#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int>val(nums.size()+2);
        val[0]=val[val.size()-1]=1;
        for(int i=1;i<=nums.size();i++)
        {
            val[i]=nums[i-1];
        }
        vector<vector<int>>dp(val.size(),vector<int>(val.size()));
        for(int i=val.size();i>=0;i--)
        {
            for(int j=i+1;j<val.size();j++)
            {
                for(int k=i+1;k<j;k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+val[i]*val[j]*val[k]);
                }
            }
        }
        return dp[0][val.size()-1];
    }
};
